package b;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86183
 * Date: 2024-04-30
 * Time: 18:20
 */
public class AVLTree {
    static class TreeNode{
        public int val;
        public int bf;
        public TreeNode left ;
        public TreeNode right;
        public TreeNode parent;
        public TreeNode(int val){
            this.val = val;
        }
    }
    public TreeNode root;
    public boolean insert(int val){
        TreeNode node = new TreeNode(val);
        if(root==null){
            root = node;
        }
        TreeNode cur = root;
        TreeNode parent =null;
        while( cur != null){
            if(cur.val<val){
                parent = cur;
                cur = cur.right;
            }else if(cur.val == val){
                return false;
            }else{
                parent = cur;
                cur = cur.left;
            }
        }
        if(parent.val<val){
            parent.right = node;
            node.parent = parent;
        }else {
            parent.left = node;
            node.parent = parent;
        }
        cur = node;
        parent = cur.parent;
        while(parent!=null){
            if(parent.right==cur){
                parent.bf++;
            }else {
                parent.bf--;
            }
            if(parent.bf==0){
                break;
            }else if(parent.bf==1 || parent.bf ==-1){
                //继续向上调整
                cur = parent;
                parent =parent.parent;
            }else{
                if(parent.bf==2){
                    if(cur.bf==1){
                        //左旋
                        rotateLeft(parent);
                    }else {
                        //右左双旋
                        rotateRL(parent);
                    }
                }else{
                    //parent.bf== -2
                    if(cur.bf==1){
                        //左右双旋
                        rotateLR(parent);
                    }else{
                        //右旋
                        rotateRight(parent);

                    }
                }
                break;
            }

        }
        return true ;
    }

    private void rotateLR(TreeNode parent) {


        TreeNode subL =parent.left;
        TreeNode subLR  = subL.right;
        rotateLeft(parent.left);
        rotateRight(parent);
        int bf  = subLR.bf;
        if(bf==-1){
            parent.bf = 1;
            subL.bf =0;
            subLR.bf =0;
        }else if(bf==1){
            subL.bf =-1;
            parent.bf=0;
            subLR.bf =0;
        }
    }

    private void rotateRL(TreeNode parent) {

        TreeNode subR =parent.right;
        TreeNode subRL= subR.left;
        int bf = subRL.bf;
        rotateRight(parent.right);
        rotateLeft(parent);
        if(bf==1){
            parent.bf =-1;
            subR.bf =0;
            subRL.bf =0;
        }else if(bf==-1){
            subR.bf =1;
            parent.bf =0;
            subRL.bf =0;
        }

    }

    private void rotateLeft(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        subR.left = parent;
        parent.right = subRL;
        TreeNode pParent = parent.parent;
        parent.parent = subR;
        if(subRL != null){
            subRL.parent = parent;
        }
        if(parent==root){
            subR = root;
            subR.parent= null;
        }else if(pParent.left == parent){

            pParent.left = subR;
            subR.parent = pParent;
        }else{
            pParent.right = subR;
            subR.parent = pParent;
        }
        parent.bf = 0;
        subR.bf =0;


    }

    private void rotateRight(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        subL.right = parent;
        parent.left = subLR;
        TreeNode pParent = parent.parent;
        parent.parent = subL;
        if(parent==root){
            subL = root;
            subL.parent = null;
        }else if(pParent.left == parent){
            pParent.left = subL;
            subL.parent = pParent;
        }else{
            pParent.right = subL;
            subL.parent = pParent;
        }
        if(subLR!=null){
            subLR.parent = parent;
        }
        parent.bf = 0;
        subL.bf = 0;



    }
    public int height(TreeNode root){
        if(root==null){
            return 0;
        }
        int leftHeight = height(root.left);
        int rightHeight = height(root.right);
        return Math.max(leftHeight,rightHeight)+1;
    }
    public boolean isBalance(TreeNode root){
      if(root==null){
          return true;
         }

      int leftH = height(root.left);
      int rightH = height(root.right);
      if(rightH-leftH != root.bf) {
            System.out.println("这个节点："+root.val+" 平衡因子异常");
            return false;
        }
      return Math.abs(leftH-rightH)<=1 && isBalance(root.left) && isBalance(root.right);



    }
}
